
#include "mian_util.h"
#include "coproc.h"
#include "buffer.h"
#include <pthread.h>



/*configuration for work stealing*/
//#define CPU_SA_BUFSIZE 				(8*((uint64)(1024*1024*1024)))		//for CPU output
//#define GPU_BUFSIZE				(2.8*((uint64)(1024*1024*1024)))	//for GPU result output
#define NUM_QUERY_PER_PASS_CPU		(100)
#define NUM_QUERY_PER_PASS_GPU		(400000)

/*the mutex and shared data by threads*/
static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
static int numFinishedQuery = 0;


/*utility macro*/
#define checkPthreadCode(string, val) {					\
	if (val) {											\
		printf("Failed with %d at %s\n", val, string);	\
		exit(1);										\
	}													\
}

#define min(a, b) (a < b) ? a : b


struct CPU2BWTThreadParam_t {
	//input parameter
	int threadId;
	unsigned int* Queries;
	unsigned int* revQueries;
	int numQuery;			//the total number of queries to be processed
	int numQueryPerPass;	//the number of queries processed per pass
	int querySizeInWord;
	BWT* bwt;
	BWT* revbwt;
	//output
	uint64 numAlign;
	uint64 numSA;
	uint3* sa;
	uint64 saBufSize;
	long* h_numAlign;
	
	
	CPU2BWTThreadParam_t(const int i_threadId,
					unsigned int* i_Queries, const int i_numQuery, 
					const int i_querySizeInWord, const int i_numQueryPerPass,
					BWT* i_bwt, BWT* i_revbwt, 
					uint3* i_sa, const uint64 i_saBufSize, 
					unsigned int* i_revQueries = NULL) {
		this->threadId = i_threadId;
		this->Queries = i_Queries;
		this->revQueries = i_revQueries;
		this->numQuery = i_numQuery;
		this->numQueryPerPass = i_numQueryPerPass;
		this->querySizeInWord = i_querySizeInWord;
		this->bwt = i_bwt;
		this->revbwt = i_revbwt;
		this->numSA = 0;
		this->numAlign = 0;
		this->sa = i_sa;
		this->saBufSize = i_saBufSize;
		
		h_numAlign = (long*)malloc(sizeof(long)*numQuery);
		memset(h_numAlign, 0, sizeof(long)*numQuery);
	};
	
	//used by the simple interfaces
	CPU2BWTThreadParam_t(const int i_threadId,
					unsigned int* i_Queries, const int i_numQuery, 
					const int i_querySizeInWord,
					BWT* i_bwt, BWT* i_revbwt, 
					uint3* i_sa, const uint64 i_saBufSize, 
					unsigned int* i_revQueries = NULL) {
		this->threadId = i_threadId;
		this->Queries = i_Queries;
		this->revQueries = i_revQueries;
		this->numQuery = i_numQuery;
		this->querySizeInWord = i_querySizeInWord;
		this->bwt = i_bwt;
		this->revbwt = i_revbwt;
		this->numSA = 0;
		this->numAlign = 0;
		this->sa = i_sa;
		this->saBufSize = i_saBufSize;

                h_numAlign = (long*)malloc(sizeof(long)*numQuery);
                memset(h_numAlign, 0, sizeof(long)*numQuery);
	};

	void close() {
		free(h_numAlign);
	}
	
	void check() {
		assert(sizeof(uint3)*this->numSA <= saBufSize);
	}
	
	uint64 calculateNumAlign() {
		check();
		numAlign = 0;
		for(uint64 i = 0; i < numSA; i++) {
			numAlign += (sa[i].z - sa[i].y + 1);
		}
		return numAlign;
	}

	uint64 calculateNumAlignLimit() {
		numAlign = 0;
		for(int i = 0; i < numQuery; i++) {
			if(h_numAlign[i] > 0) {
				numAlign += h_numAlign[i];
			}
		}
		
		return numAlign;
	}
};


struct GPU2BWTThreadParam_t {
	//input parameter
	int threadId;
	unsigned int* Queries;
	unsigned int* revQueries;
	int numQuery;			//the total number of queries to be processed
	int numQueryPerPass;	//the number of queries processed per pass
	int querySizeInWord;
	BWT* d_bwt;
	BWT* d_revbwt;
	st_MemoryBuf* GPUMemBuf;
	//output
	uint64 numAlign;	
	long* d_numAlign;
	//the cpu output buffere
	uint3* cpuSA;
	uint* numSA;
	
	GPU2BWTThreadParam_t(		uint3* i_cpuSA, uint* i_numSA,
					const int i_threadId,
					unsigned int* i_Queries, const int i_numQuery, 
					const int i_querySizeInWord, const int i_numQueryPerPass,
					BWT* i_bwt, BWT* i_revbwt, st_MemoryBuf* i_GPUMemBuf, 
					unsigned int* i_revQueries = NULL) {
		this->threadId = i_threadId;
		this->Queries = i_Queries;
		this->revQueries = i_revQueries;
		this->numQuery = i_numQuery;
		this->numQueryPerPass = i_numQueryPerPass;
		this->querySizeInWord = i_querySizeInWord;
		this->d_bwt = i_bwt;
		this->d_revbwt = i_revbwt;
		this->GPUMemBuf = i_GPUMemBuf;
		this->cpuSA = i_cpuSA;
		this->numSA = i_numSA;
		
		this->numAlign = 0;
		GPUMALLOC((void**)&d_numAlign, sizeof(long)*numQuery);
		cutilSafeCall(cudaMemset(d_numAlign, 0, sizeof(long)*numQuery));
	};

        GPU2BWTThreadParam_t(const int i_threadId,
                                        unsigned int* i_Queries, const int i_numQuery,
                                        const int i_querySizeInWord, const int i_numQueryPerPass,
                                        BWT* i_bwt, BWT* i_revbwt, st_MemoryBuf* i_GPUMemBuf,
                                        unsigned int* i_revQueries = NULL) {
                this->threadId = i_threadId;
                this->Queries = i_Queries;
                this->revQueries = i_revQueries;
                this->numQuery = i_numQuery;
                this->numQueryPerPass = i_numQueryPerPass;
                this->querySizeInWord = i_querySizeInWord;
                this->d_bwt = i_bwt;
                this->d_revbwt = i_revbwt;
                this->GPUMemBuf = i_GPUMemBuf;

                this->numAlign = 0;
                GPUMALLOC((void**)&d_numAlign, sizeof(long)*numQuery);
                cutilSafeCall(cudaMemset(d_numAlign, 0, sizeof(long)*numQuery));
        };
	
	GPU2BWTThreadParam_t(		uint3* i_cpuSA, uint* i_numSA,
					const int i_threadId,
					unsigned int* i_Queries, const int i_numQuery, 
					const int i_querySizeInWord,
					BWT* i_bwt, BWT* i_revbwt, st_MemoryBuf* i_GPUMemBuf, 
					unsigned int* i_revQueries = NULL) { 
		this->threadId = i_threadId;
		this->Queries = i_Queries;
		this->revQueries = i_revQueries;
		this->numQuery = i_numQuery;
		this->querySizeInWord = i_querySizeInWord;
		this->d_bwt = i_bwt;
		this->d_revbwt = i_revbwt;
		this->GPUMemBuf = i_GPUMemBuf;
		this->cpuSA = i_cpuSA;
		this->numSA = i_numSA;
		
		this->numAlign = 0;
                GPUMALLOC((void**)&d_numAlign, sizeof(long)*numQuery);
                cutilSafeCall(cudaMemset(d_numAlign, 0, sizeof(long)*numQuery));
	};


        GPU2BWTThreadParam_t(const int i_threadId,
                                        unsigned int* i_Queries, const int i_numQuery,
                                        const int i_querySizeInWord,
                                        BWT* i_bwt, BWT* i_revbwt, st_MemoryBuf* i_GPUMemBuf,
                                        unsigned int* i_revQueries = NULL) {
                this->threadId = i_threadId;
                this->Queries = i_Queries;
                this->revQueries = i_revQueries;
                this->numQuery = i_numQuery;
                this->querySizeInWord = i_querySizeInWord;
                this->d_bwt = i_bwt;
                this->d_revbwt = i_revbwt;
                this->GPUMemBuf = i_GPUMemBuf;

                this->numAlign = 0;
                GPUMALLOC((void**)&d_numAlign, sizeof(long)*numQuery);
                cutilSafeCall(cudaMemset(d_numAlign, 0, sizeof(long)*numQuery));
        };

	void close() {
		GPUFREE(d_numAlign);
	}

	uint64 calculateNumAlignLimit() {
		long* h_numAlign = (long*)malloc(sizeof(long)*numQuery);
		FROMGPU(h_numAlign, d_numAlign, sizeof(long)*numQuery);
		numAlign = 0;

		for(int i = 0; i < numQuery; i++) {
			if(h_numAlign[i] > 0) {
				numAlign += h_numAlign[i];
			}
		}
		
		free(h_numAlign);	

		return numAlign;
	}
};



void swap(unsigned int* oldval, unsigned int* newval) {
	unsigned int tmp = *oldval;
	*oldval = *newval;
	*newval = tmp;
}

void shuffleQuery(unsigned int* query, 
				const int numQuery, const int querySizeInWord, 
				unsigned int seed) {
	srand(seed);
	printf("RAND_MAX: %lu\n", RAND_MAX);
	assert(RAND_MAX >= numQuery);
	
	for(int oldQueryId = 0; oldQueryId < numQuery; oldQueryId++) {
		const int newQueryId = rand()%numQuery;
		for(int wordId = 0; wordId < querySizeInWord; wordId++) {
			swap(&(query[querySizeInWord*oldQueryId + wordId]), 
				&(query[querySizeInWord*newQueryId + wordId]));
		}
	}
	printf("Query shuffle done.\n");
}



void* cpuThread(void* param) {
	CPU2BWTThreadParam_t* CPU2BWTThreadParam = (CPU2BWTThreadParam_t*)param;
	int rc = 0;
	int startQueryId = 0;
	CPU2BWTThreadParam->numSA = 0;
	CPU2BWTThreadParam->numAlign = 0;
	int numQueryDone = 0;
	INIT_TIMER;

	START_TIMER;
	while(true) {
	
		//////////////////////////////////////////////////
		//critical section
		rc = pthread_mutex_lock(&mutex);
		checkPthreadCode("pthread_mutex_lock", rc);
		
		startQueryId = numFinishedQuery;
		numFinishedQuery += CPU2BWTThreadParam->numQueryPerPass;
		
		rc = pthread_mutex_unlock(&mutex);
		checkPthreadCode("pthread_mutex_unlock", rc);
		//end critical section
		//////////////////////////////////////////////////
		
		//stop if all queries have been processed
		if(startQueryId >= CPU2BWTThreadParam->numQuery) {
			break;
		}
	
		//otherwise process this pass of query
		const int numQueryProcess = min(CPU2BWTThreadParam->numQueryPerPass, 
										CPU2BWTThreadParam->numQuery - startQueryId);
		//printf("thread %d, startQueryId %d, numQueryProcess %d\n", 
		//		CPU2BWTThreadParam->threadId, startQueryId, numQueryProcess);
		CPU2BWTThreadParam->numSA +=	
									CPU2BWTSearch(CPU2BWTThreadParam->sa + CPU2BWTThreadParam->numSA, 
									CPU2BWTThreadParam->Queries + CPU2BWTThreadParam->querySizeInWord*startQueryId, 
									numQueryProcess, 
									CPU2BWTThreadParam->bwt, 
									CPU2BWTThreadParam->revbwt);
		CPU2BWTThreadParam->check();
		numQueryDone += numQueryProcess;
	}	
	END_TIMER;
	assert(numFinishedQuery >= CPU2BWTThreadParam->numQuery);
	
	CPU2BWTThreadParam->calculateNumAlign();
	
	printf("thread %d done, #query processed %d, #align %lu\n", 
			CPU2BWTThreadParam->threadId, numQueryDone, CPU2BWTThreadParam->numAlign);
	PRINT_TIMER_SEC("CPU thread time");
}




void* cpuThread_simple(void* param) {
	CPU2BWTThreadParam_t* CPU2BWTThreadParam = (CPU2BWTThreadParam_t*)param;
	int rc = 0;
	CPU2BWTThreadParam->numSA = 0;
	CPU2BWTThreadParam->numAlign = 0;
	INIT_TIMER;
	START_TIMER;

	CPU2BWTThreadParam->numSA += CPU2BWTSearch(CPU2BWTThreadParam->sa, 
								CPU2BWTThreadParam->Queries, 
								CPU2BWTThreadParam->numQuery, 
								CPU2BWTThreadParam->bwt, 
								CPU2BWTThreadParam->revbwt);
	CPU2BWTThreadParam->check();
	CPU2BWTThreadParam->calculateNumAlign();
	END_TIMER;
	
	printf("thread %d done, #query processed %d, #align %lu\n", 
			CPU2BWTThreadParam->threadId, 
			CPU2BWTThreadParam->numQuery, 
			CPU2BWTThreadParam->numAlign);
	PRINT_TIMER_SEC("CPU thread time");
}



void* cpuThreadLimit_simple(void* param) {
	CPU2BWTThreadParam_t* CPU2BWTThreadParam = (CPU2BWTThreadParam_t*)param;
	int rc = 0;
	CPU2BWTThreadParam->numSA = 0;
	CPU2BWTThreadParam->numAlign = 0;
	memset(CPU2BWTThreadParam->h_numAlign, 0, sizeof(long)*CPU2BWTThreadParam->numQuery);
	INIT_TIMER;
	START_TIMER;


	CPU2BWTSearchTwoStrandLimit(CPU2BWTThreadParam->h_numAlign, CPU2BWTThreadParam->sa, 
					CPU2BWTThreadParam->Queries, CPU2BWTThreadParam->revQueries,
                                        CPU2BWTThreadParam->numQuery, 
					CPU2BWTThreadParam->bwt, CPU2BWTThreadParam->revbwt);
	CPU2BWTThreadParam->calculateNumAlignLimit();
	END_TIMER;
	
	printf("thread %d done, #query processed %d, #align %lu\n", 
			CPU2BWTThreadParam->threadId, 
			CPU2BWTThreadParam->numQuery, 
			CPU2BWTThreadParam->numAlign);
	PRINT_TIMER_SEC("CPU thread time");
}





void* gpuThread(void* param) {
	GPU2BWTThreadParam_t* GPU2BWTThreadParam = (GPU2BWTThreadParam_t*)param;
	int rc = 0;
	int startQueryId = 0;
	int n = 0;
	GPU2BWTThreadParam->numAlign = 0;
	INIT_TIMER;
	START_TIMER;

	while(true) {
	
		//////////////////////////////////////////////////
		//critical section
		rc = pthread_mutex_lock(&mutex);
		checkPthreadCode("pthread_mutex_lock", rc);
		
		startQueryId = numFinishedQuery;
		numFinishedQuery += GPU2BWTThreadParam->numQueryPerPass;
		
		rc = pthread_mutex_unlock(&mutex);
		checkPthreadCode("pthread_mutex_unlock", rc);
		//end critical section
		//////////////////////////////////////////////////
		
		//stop if all queries have been processed
		if(startQueryId >= GPU2BWTThreadParam->numQuery) {
			break;
		}
	
		//otherwise process this pass of query
		const int numQueryProcess = min(GPU2BWTThreadParam->numQueryPerPass, 
										GPU2BWTThreadParam->numQuery - startQueryId);
		printf("***GPU thread %d***, startQueryId %d, numQueryProcess %d\n", 
				GPU2BWTThreadParam->threadId, startQueryId, numQueryProcess);
/*		GPU2BWTThreadParam->numAlign += GPU2BWTSearch(GPU2BWTThreadParam->Queries + GPU2BWTThreadParam->querySizeInWord*startQueryId, 
											numQueryProcess, 
											GPU2BWTThreadParam->d_bwt, 
											GPU2BWTThreadParam->d_revbwt, 
											GPU2BWTThreadParam->GPUMemBuf);
*/		n += numQueryProcess;
		GPU2BWTThreadParam->GPUMemBuf->reset();
	}	
	END_TIMER;
	
	
	printf("GPU thread %d done, #queries processed %d, #align = %lu\n", 
			GPU2BWTThreadParam->threadId, n, GPU2BWTThreadParam->numAlign);
	PRINT_TIMER_SEC("GPU thread time");
}



void* gpuThread_simple(void* param) {
	GPU2BWTThreadParam_t* GPU2BWTThreadParam = (GPU2BWTThreadParam_t*)param;
	int rc = 0;
	GPU2BWTThreadParam->numAlign = 0;
	INIT_TIMER;
	START_TIMER;

	/*
	GPU2BWTThreadParam->numAlign += GPU2BWTSearch(GPU2BWTThreadParam->Queries, 
										GPU2BWTThreadParam->numQuery, 
										GPU2BWTThreadParam->d_bwt, 
										GPU2BWTThreadParam->d_revbwt, 
										GPU2BWTThreadParam->GPUMemBuf);
	*/
	*(GPU2BWTThreadParam->numSA) = 0;
	GPU2BWTThreadParam->numAlign += GPU2BWTSearch_shareBuf(		
									GPU2BWTThreadParam->Queries, 
									GPU2BWTThreadParam->numQuery,
									GPU2BWTThreadParam->d_bwt,
									GPU2BWTThreadParam->d_revbwt, 
									GPU2BWTThreadParam->GPUMemBuf, 
                                                                        GPU2BWTThreadParam->cpuSA,
                                                                        GPU2BWTThreadParam->numSA); 
	GPU2BWTThreadParam->GPUMemBuf->reset();
	END_TIMER;
	
	printf("GPU thread %d done, #align = %lu\n", 
			GPU2BWTThreadParam->threadId, GPU2BWTThreadParam->numAlign);
	PRINT_TIMER_SEC("GPU thread time");
}




void* gpuThreadLimit_simple(void* param) {
	GPU2BWTThreadParam_t* GPU2BWTThreadParam = (GPU2BWTThreadParam_t*)param;
	int rc = 0;
	GPU2BWTThreadParam->numAlign = 0;
	cutilSafeCall(cudaMemset(GPU2BWTThreadParam->d_numAlign, 0, sizeof(long)*GPU2BWTThreadParam->numQuery));
	INIT_TIMER;
	START_TIMER;

	/*
	GPU2BWTSearchTwoStrandLimit(GPU2BWTThreadParam->d_numAlign, 
				GPU2BWTThreadParam->Queries, GPU2BWTThreadParam->revQueries, 
				GPU2BWTThreadParam->numQuery, 
				GPU2BWTThreadParam->d_bwt, GPU2BWTThreadParam->d_revbwt, 
				GPU2BWTThreadParam->GPUMemBuf);
	*/
	GPU2BWTSearchLimit(GPU2BWTThreadParam->d_numAlign, 
				GPU2BWTThreadParam->Queries, GPU2BWTThreadParam->numQuery, 
				GPU2BWTThreadParam->d_bwt, GPU2BWTThreadParam->d_revbwt, 
				GPU2BWTThreadParam->GPUMemBuf, 
				GPU2BWTThreadParam->cpuSA, 
				GPU2BWTThreadParam->numSA);
	GPU2BWTThreadParam->calculateNumAlignLimit();
	GPU2BWTThreadParam->GPUMemBuf->reset();
	END_TIMER;
	
	printf("GPU thread %d done, #align = %lu\n", 
			GPU2BWTThreadParam->threadId, GPU2BWTThreadParam->numAlign);
	PRINT_TIMER_SEC("GPU thread time");
}




//simple workload partitioning for the workload
uint64 coproc2BWTSearch_simple(unsigned int* Queries, const int numQuery, 
				BWT* bwt, BWT* revbwt, BWT* d_bwt, BWT* d_revbwt, st_MemoryBuf* GPUMemBuf,
				const int numCPUThread, 
				uint64 bufSize, uint3* cpuSABuf, uint32* numSA) {
	PRINT_FUNC_NAME;	

	printf(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n");
		
	int rc = 0;
	uint64 numAlign = 0;
	const int numQueryGPU = numQuery*0.5;
	const int numQueryCPU = numQuery - numQueryGPU;
	const int numTotalThread = numCPUThread + 1;

	printf("numQueryGPU: %d, numQueryCPU: %d, numCPUThread: %d\n", 
		numQueryGPU, numQueryCPU, numCPUThread);
	
	
					
	/*CPU initialization*/
	//CPU2BWTInit(bwt, revbwt);
	
	/*assign the result memory buffer on the CPU*/
	uint3** cpuSA = (uint3**)malloc(sizeof(uint3*)*numTotalThread); 
	const uint64 cpuSABufSizePerThread = bufSize/numTotalThread;
	for(int i = 0; i < numTotalThread; i++) {
		cpuSA[i] = (uint3*)((unsigned char*)cpuSABuf + i*cpuSABufSizePerThread);
	}
	uint32* numSAPerThread = (uint32*)malloc(sizeof(uint32)*numTotalThread);
	
	
	
	/*GPU initialization*/
	/*BWT * d_bwt = NULL;
	BWT * d_revbwt = NULL;*/
	//GPUMemBuf = new st_MemoryBuf(GPU_BUFSIZE, GMEM);
	//GPU2BWTInit(&d_bwt, &d_revbwt, bwt, revbwt, &GPUMemBuf, GPU_BUFSIZE);
	//printf("GPU2BWTInit_bufOnly done.\n");
	
	/*pthread initialization*/
	pthread_t* thread = new pthread_t[numTotalThread];
	GPU2BWTThreadParam_t* GPU2BWTThreadParam = new GPU2BWTThreadParam_t
					(cpuSA[0], &(numSAPerThread[0]), 0,
					Queries, numQueryGPU, 
					QUERY_SIZE_IN_WORD,
					d_bwt, d_revbwt, GPUMemBuf);
	int queryOffset = numQueryGPU;
	const int numQueryPerCPUThread = numQueryCPU/numCPUThread;
	CPU2BWTThreadParam_t** CPU2BWTThreadParam = 
				(CPU2BWTThreadParam_t**)malloc(numCPUThread*sizeof(CPU2BWTThreadParam_t*));
	for(int i = 0; i < numCPUThread; i++) {
		const int numQueryProcess = (i == (numCPUThread - 1)) ? 
									(numQueryCPU - i*numQueryPerCPUThread) : 
									(numQueryPerCPUThread);
		const int queryCPUOffset = i*numQueryPerCPUThread;
		CPU2BWTThreadParam[i] = new CPU2BWTThreadParam_t
					(i + 1,
					Queries + QUERY_SIZE_IN_WORD*(numQueryGPU + queryCPUOffset), 
					numQueryProcess, QUERY_SIZE_IN_WORD,
					bwt, revbwt, cpuSA[i + 1], cpuSABufSizePerThread);
	}
	
	/*GPU-CPU coprocessing*/
	INIT_TIMER;
	START_TIMER;
	rc = pthread_create(&(thread[0]), NULL, gpuThread_simple, GPU2BWTThreadParam);
	checkPthreadCode("pthread_create", rc);
	for(int i = 1; i < numTotalThread; i++) {
		rc = pthread_create(&(thread[i]), NULL, cpuThread_simple, CPU2BWTThreadParam[i - 1]);
		checkPthreadCode("pthread_create", rc);
	}
	for (int i = 0; i < numTotalThread; ++i) {
		rc = pthread_join(thread[i], NULL);
		checkPthreadCode("pthread_join", rc);
	}
	END_TIMER;
	
	/*report result*/
	printf("all processing threads are done.\n");
	numAlign = 0;
	numAlign += GPU2BWTThreadParam->numAlign;
	for(int i = 0; i < numCPUThread; i++) {
			numAlign += CPU2BWTThreadParam[i]->numAlign;
	}
	printf("========> numAlignment = %lu\n", numAlign);
	PRINT_TIMER_SEC("GPU-CPU coprocessing time");
	

	//check the result
	numSAPerThread[0] = *(GPU2BWTThreadParam->numSA);
	assert(sizeof(uint3)*numSAPerThread[0] <= cpuSABufSizePerThread);
	*numSA = numSAPerThread[0];
	for(int i = 1; i < numTotalThread; i++) {
		numSAPerThread[i] = CPU2BWTThreadParam[i - 1]->numSA;
		*numSA += numSAPerThread[i];
		assert(sizeof(uint3)*numSAPerThread[i] <= cpuSABufSizePerThread);
	}
	
	//now we have to compact the result.....
	uint64 offset = numSAPerThread[0];
	for(int i = 1; i < numTotalThread; i++) {
		memcpy(cpuSABuf + offset, cpuSA[i], sizeof(uint3)*numSAPerThread[i]);
		offset += numSAPerThread[i];
	}
	assert(offset == *numSA);
	
	/*cleanup*/
	rc = pthread_mutex_destroy(&mutex);
	//CPUMemBuf->close();
	//GPUMemBuf->close();
	free(cpuSA);
	free(numSAPerThread);

	return numAlign;
}



//simple workload partitioning for the workload
uint64 coproc2BWTSearchLimit_simple(unsigned int* Queries, const int numQuery, 
						BWT* bwt, BWT* revbwt, BWT* d_bwt, BWT* d_revbwt, st_MemoryBuf* GPUMemBuf,
						const int numCPUThread, 
						uint64 bufSize, uint3* cpuSABuf, uint32* numSA) {
	PRINT_FUNC_NAME;	

	printf(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n");
		
	int rc = 0;
	uint64 numAlign = 0;
	const int numQueryGPU = numQuery*0.5;
	const int numQueryCPU = numQuery - numQueryGPU;
	const int numTotalThread = numCPUThread + 1;
	
	
	/*assign the result memory buffer on the CPU*/
	uint3** cpuSA = (uint3**)malloc(sizeof(uint3*)*numTotalThread); 
	const uint64 cpuSABufSizePerThread = bufSize/numTotalThread;
	for(int i = 0; i < numTotalThread; i++) {
		cpuSA[i] = (uint3*)((unsigned char*)cpuSABuf + i*cpuSABufSizePerThread);
	}
	uint32* numSAPerThread = (uint32*)malloc(sizeof(uint32)*numTotalThread);
	
	

	
	/*pthread initialization*/
	pthread_t* thread = new pthread_t[numTotalThread];
	GPU2BWTThreadParam_t* GPU2BWTThreadParam = new GPU2BWTThreadParam_t
					(cpuSA[0], &(numSAPerThread[0]), 0,
					Queries, numQueryGPU, 
					QUERY_SIZE_IN_WORD,
					d_bwt, d_revbwt, GPUMemBuf);
	int queryOffset = numQueryGPU;
	const int numQueryPerCPUThread = numQueryCPU/numCPUThread;
	CPU2BWTThreadParam_t** CPU2BWTThreadParam = 
				(CPU2BWTThreadParam_t**)malloc(numCPUThread*sizeof(CPU2BWTThreadParam_t*));
	for(int i = 0; i < numCPUThread; i++) {
		const int numQueryProcess = (i == (numCPUThread - 1)) ? 
									(numQueryCPU - i*numQueryPerCPUThread) : 
									(numQueryPerCPUThread);
		const int queryCPUOffset = i*numQueryPerCPUThread;
		CPU2BWTThreadParam[i] = new CPU2BWTThreadParam_t
					(i + 1,
					Queries + QUERY_SIZE_IN_WORD*(numQueryGPU + queryCPUOffset), 
					numQueryProcess, QUERY_SIZE_IN_WORD,
					bwt, revbwt, cpuSA[i + 1], cpuSABufSizePerThread);
	}
	
	/*GPU-CPU coprocessing*/
	INIT_TIMER;
	START_TIMER;
	rc = pthread_create(&(thread[0]), NULL, gpuThreadLimit_simple, GPU2BWTThreadParam);
	checkPthreadCode("pthread_create", rc);
	for(int i = 1; i < numTotalThread; i++) {
		rc = pthread_create(&(thread[i]), NULL, cpuThreadLimit_simple, CPU2BWTThreadParam[i - 1]);
		checkPthreadCode("pthread_create", rc);
	}
	for (int i = 0; i < numTotalThread; ++i) {
		rc = pthread_join(thread[i], NULL);
		checkPthreadCode("pthread_join", rc);
	}
	END_TIMER;
	
	/*report result*/
	printf("all processing threads are done.\n");
	PRINT_TIMER_SEC("GPU-CPU coprocessing time");
	

	//check the result
	numSAPerThread[0] = *(GPU2BWTThreadParam->numSA);
	assert(sizeof(uint3)*numSAPerThread[0] <= cpuSABufSizePerThread);
	*numSA = numSAPerThread[0];
	for(int i = 1; i < numTotalThread; i++) {
		numSAPerThread[i] = CPU2BWTThreadParam[i - 1]->numSA;
		*numSA += numSAPerThread[i];
		assert(sizeof(uint3)*numSAPerThread[i] <= cpuSABufSizePerThread);
	}
	
	//now we have to compact the result.....
	uint64 offset = numSAPerThread[0];
	for(int i = 1; i < numTotalThread; i++) {
		memcpy(cpuSABuf + offset, cpuSA[i], sizeof(uint3)*numSAPerThread[i]);
		offset += numSAPerThread[i];
	}
	assert(offset == *numSA);
	
	/*cleanup*/
	rc = pthread_mutex_destroy(&mutex);
	free(cpuSA);
	free(numSAPerThread);

	return numAlign;
}





//with the work stealing approach
void coproc2BWTSearch(unsigned int* Queries, const int numQuery, 
						BWT* bwt, BWT* revbwt,
						const int numCPUThread) {
	PRINT_FUNC_NAME;
	printf("numCPUThread = %d\n", numCPUThread);
					
	int rc = 0;
	uint64 numAlign = 0;
					
	/*CPU initialization*/
	CPU2BWTInit(bwt, revbwt);
	st_MemoryBuf* CPUMemBuf = new st_MemoryBuf(CPU_SA_BUFSIZE, CMEM);
	uint3** cpuSA = (uint3**)malloc(sizeof(uint3*)*numCPUThread);
	const uint64 cpuSABufSizePerThread = CPU_SA_BUFSIZE/numCPUThread;
	for(int i = 0; i < numCPUThread; i++) {
		cpuSA[i] = (uint3*)CPUMemBuf->newMem(cpuSABufSizePerThread);
	}
	
	
	
	/*GPU initialization*/
	BWT * d_bwt = NULL;
	BWT * d_revbwt = NULL;	
	st_MemoryBuf* GPUMemBuf = NULL;
	GPU2BWTInit(&d_bwt, &d_revbwt, bwt, revbwt, &GPUMemBuf, GPU_BUFSIZE);
	
	
	
	/*pthread initialization*/
	pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
	numFinishedQuery = 0;
	const int numTotalThread = numCPUThread + 1;
	pthread_t* thread = new pthread_t[numTotalThread];
	GPU2BWTThreadParam_t* GPU2BWTThreadParam = new GPU2BWTThreadParam_t(0,
										Queries, numQuery, QUERY_SIZE_IN_WORD, NUM_QUERY_PER_PASS_GPU,
										d_bwt, d_revbwt, GPUMemBuf);
	CPU2BWTThreadParam_t** CPU2BWTThreadParam = 
				(CPU2BWTThreadParam_t**)malloc(numCPUThread*sizeof(CPU2BWTThreadParam_t*));
	for(int i = 0; i < numCPUThread; i++) {
		CPU2BWTThreadParam[i] = new CPU2BWTThreadParam_t(i + 1, Queries, numQuery, 
								QUERY_SIZE_IN_WORD, NUM_QUERY_PER_PASS_CPU,
								bwt, revbwt, 
								cpuSA[i], cpuSABufSizePerThread);
	}

	

	/*GPU-CPU coprocessing*/
	INIT_TIMER;
	START_TIMER;
	rc = pthread_create(&(thread[0]), NULL, gpuThread, GPU2BWTThreadParam);
	checkPthreadCode("pthread_create", rc);
	for(int i = 1; i < numTotalThread; i++) {
		rc = pthread_create(&(thread[i]), NULL, cpuThread, CPU2BWTThreadParam[i - 1]);
		checkPthreadCode("pthread_create", rc);
	}
	for (int i = 0; i < numTotalThread; ++i) {
		rc = pthread_join(thread[i], NULL);
		checkPthreadCode("pthread_join", rc);
	}
	
/////////////////
//if only CPU threads
/*	printf("===> NOTE: actually there are only CPU threads");
	for(int i = 1; i < numTotalThread; i++) {
		rc = pthread_create(&(thread[i]), NULL, cpuThread, CPU2BWTThreadParam[i - 1]);
		checkPthreadCode("pthread_create", rc);
	}
	for (int i = 1; i < numTotalThread; ++i) {
		rc = pthread_join(thread[i], NULL);
		checkPthreadCode("pthread_join", rc);
	}
	*/
//if only GPU thread
/*	printf("===> NOTE: actually there is only one GPU thread");
	rc = pthread_create(&(thread[0]), NULL, gpuThread, GPU2BWTThreadParam);
	checkPthreadCode("pthread_create", rc);
	rc = pthread_join(thread[0], NULL);
	checkPthreadCode("pthread_join", rc);
	*/
////
	END_TIMER;
	
	
	/*report result*/
	printf("all processing threads are done.\n");
	numAlign = 0;
	numAlign += GPU2BWTThreadParam->numAlign;
	for(int i = 0; i < numCPUThread; i++) {
		numAlign += CPU2BWTThreadParam[i]->numAlign;
	}
	printf("========> numAlignment = %lu\n", numAlign);
	PRINT_TIMER_SEC("GPU-CPU coprocessing time");
	
	
	/*cleanup*/
	rc = pthread_mutex_destroy(&mutex);
	CPUMemBuf->close();
	GPUMemBuf->close();
	free(cpuSA);
}


